perm filename VITABI[AM,DBL] blob
sn#694520 filedate 1983-01-11 generic text, type T, neo UTF8
Douglas B. Lenat
Personal Data
Office address: 230 Margaret Jacks Hall
Computer Science Dept.
Stanford University
Stanford, Ca. 94305
Telephone: 415-497-0304
Home address: 1752 Selig Lane
Los Altos, Ca. 94022
Telephone: 415-965-1228
Born: September 13, 1950, Philadelphia, Pa.
Citizenship: USA
Married: June 4, 1972
Wife: Merle Ellyn Lenat
Daughter: Nicolle Danielle Lenat (11/12/80)
Degrees Conferred
B.A. Mathematics, U. of Pa., June, 1972
B.A. Physics, U. of Pa., June, 1972
M.S. Applied Mathematics, U. of Pa., June, 1972
Ph.D. Computer Science, Stanford U., September, 1976
Scientific Investigations
1969: Natural Language interface to U. S. Navy data base question-answering
system.
1970: Electron-electron scattering [as a research assistant to Dr. Walter
Selove, Professor of experimental high-energy physics at the University
of Pennsylvania].
1971: Acoustic Holography in Air at 40mHz. [Physics senior thesis].
1972: Computer-generated holograms of 3D projections of four-dimensional
objects, and reconstruction by normal laser imaging.
1973: Simple automatic programming systems, using program template instantiation
techniques: PW1, SEW, PUP. Described in [1].
1974: PUP6: an automatic programming system capable of generating a few
ten-page long LISP concept-formation programs, from very constrained English
dialogues. Described in [2,4].
1975: AM: a heuristic search program capable of performing simple math research.
Described in [3,5,6].
1977: Architectures for rule-based computation systems. Discussed in [6,8,11].
See also [10].
1978-80: EURISKO: successor to AM. Designed to (a) discover new heuristics,
(b) develop journal-caliber mathematics, and (c) build models of its users.
See [9,19,21].
1979-80: Applying AI ideas to biology; specifically, work on the hypothesis
that evolution may by now proceed via plausible generation of mutations. [20]
1980: RLL: a Representation Language Language, a knowledge engineering tool
to facilitate development of EURISKO. See [21,23].
1980-3: Theory of heuristics: inquiry into the nature of heuristic reasoning,
the source of power, the types of heuristics, a principled approach to
determining what attributes should be meaningful for heuristics. See [19].
Published Papers
[1] Progress Report on Program-Understanding Systems, Memo AIM-240, CS Report
STAN-CS-74-444, Artificial Intelligence Laboratory, Stanford University,
August, 1974. Co-authored with Green, Waldinger, Barstow, Elshlager, McCune,
Shaw, and Steinberg.
[2] Synthesis of Large Programs from Specific Dialogues, Proceedings of
the International Symposium on Proving and Improving Programs, IRIA, Le
Chesnay, France, July, 1975.
[3] Duplication of Human Actions by an Interacting Community of Knowledge
Modules, Proceedings of the Third International Congress of Cybernetics
and Systems, Bucharest, Romania, August, 1975.
[4] BEINGS: Knowledge as Interacting Experts, Proceedings of the Fourth
International Joint Conference on Artificial Intelligence, Tbilisi, USSR,
September, 1975.
[5] AM: An Artificial Intelligence Approach to Discovery in Mathematics
as Heuristic Search, Ph.D. Thesis, Stanford A. I. Lab Memo Memo AIM-286,
CS Report No. STAN-CS-76-570, and Heuristic Programming Project Report
HPP-76-8, Stanford University, July, 1976.
[6] Designing a Rule System That Searches for Scientific Discoveries, (Lenat
and Harris), invited paper for the conference in Honolulu, May, 1977;
published in (Hayes-Roth and Waterman, eds.) Proceedings of the Conference
on Pattern-Directed Inference, Academic Press, 1977. Also issued as a CMU
technical report, April, 1977.
[7] Automated Theory Formation in Mathematics, Fifth IJCAI, Cambridge, Mass.,
August, 1977.
[8] Less Than General Production System Architectures, (Lenat and J.
McDermott,) Fifth IJCAI, Cambridge, Mass., August, 1977.
[9] The Ubiquity of Discovery, the 1977 Computers and Thought Lecture
(invited talk at the Fifth IJCAI). Preliminary version published in the
proceedings of that conference; final version printed in the Journal of
A.I. Repeated as an invited talk at NCC (Anaheim, June, 1978).
[10] Pattern Directed Inference Rules the Waves, Journal of the AISB (Artificial
Intelligence Society of Britain), October, 1977, 8-12. Reprinted in SIGART,
1978.
[11] Rule Based Computation: Some Syntheses, (Hayes-Roth, Waterman, and
Lenat), concluding chapter for (Hayes-Roth and Waterman, eds.) Proceedings
of the Conference on Pattern-Directed Inference, Academic Press, 1977.
[12] Artificial Intelligence and Natural Statistics, invited paper at "Computer
Science and Statistics: Eleventh Annual Symposium on the Interface", University
of North Carolina at Raleigh, March 6, 1978.
[13] Unscripted interview on AI & Problem Solving, broadcast over the BBC,
as part of the Open University's 32 week course on Cognitive Psychology.
Taped at CMU on Feb. 22, 1978, by Clive Holloway, Open University, Milton
Keynes, England.
[14] On Astrophysics and Superhuman Performance,
Journal of the Behavioral and Brain Sciences, Vol. 1, No. 1, 1978.
[15] On Automated Scientific Theory Formation: A Case Study Using the AM
Program, in (Michie, ed.) Machine Intelligence 9, 1979.
[16] Programs that Acquire Expert Knowledge: Two AI Approaches, (Davis
& Lenat), McGraw Hill, 1980, 390pp.
[17] Machine Perception, Invited talk at the AAAS annual meeting,
San Francisco, January, 1979.
[18] Cognitive Economy in Artificial Intelligence Systems,
Proc. Sixth IJCAI, Tokyo, 1979, 531-6. (Lenat, Hayes-Roth, and
Klahr) Also issued as HPP-79-15, and submitted to J. Cognitive Science.
[19] Toward a Theory of Heuristics, HPP-80-26, CS Dept, Stanford, 1980.
Invited talk at the Bern conference on Heuristics. Submitted to the Journal
of Artificial Intelligence.
[20] The Plausible Mutation of DNA, HPP-80-27, CS Dept, Stanford, 1980.
Submitted to Science.
[21] A Representation Language Language, Proc. First AAAI Conference, Stanford,
1980.
[22] Knowledge Engineering, an invited tutorial at the First AAAI Conf, Stanford,
1980. Videotape publication and distribution.
[23] Meta-Description and Modifiability in a Knowledge Representation
System, (Genesereth & Lenat) HPP-80-18, CS Dept, Stanford, 1980.
To be submitted to the Journal of Artificial Intelligence.
[24] Building Expert Systems, (Hayes-Roth, Waterman, and Lenat, eds.), San
Diego, Addison Wesley, 1983.
Interests
My main research interest is Discovery: Can we understand how people
synthesize new ideas? I test my hypotheses by building computer programs
which attempt to make discoveries. Experimenting with the programs leads
to criticism and improvment of the original hypotheses, to a slightly
deeper understanding of human creativity. Many issues must be dealt with
in constructing such programs: how to represent expert knowledge
concretely, how to judge the worth of new discoveries, the difficulty (and
frequency) of discoveries in various human fields of endeavor, when to
reason symbolically and inductively (and slowly) versus when to reason
statistically from frequency data (and hence quickly), what the
architecture -- the design constraints -- of such reasoning programs might
be, etc.
The long-range goal of such research is "mental enhancement" of Man, just
as medicine strives toward biological enhancement (e.g., immunization),
and as engineering strives toward physical enhancement (e.g.,
automobiles). In de-mystifying the creative process, we take the first
halting steps toward a science of discovery, toward a science of Science.
Research at Stanford
During the past two years at Stanford, my research has been threefold.
(1) My earlier research led me to conclude that new concepts can only be
discovered in conjunction with new specific heuristics, judgmental rules
which are necessary to guide the discoverer effectively in the new areas.
It seemed that this capacity in turn demanded some abilities to develop
new representations for knowledge, in conjunction with new heuristics. One
major are of my research has been this relationship between representation
and discovery. This has led to (i) a new kind of tool for easily --
automatically -- developing new representation systems [21,23], and (ii)
some insights into the nature of heuristics, their origin and sources of
power, the nature of the space of heuristics, etc.[19]
(2) Now armed with an experimental tool for investigating the discovery of
new heuristics, I have begun to build Eurisko, a program with expertise in
several specific domains, including set theory, number theory, graph
theory, geography, and biology, and some information in other fields (oil
spills, games, programming). Its task is to develop new concepts in those
fields, and find plausible conjectures connecting them. This is much what
AM did. In addition, I have become convinced of the potency of proof as
an instrument of discovery, and the Eurisko system has knowledge of proof
types and techniques. But the chief advances of Eurisko over AM are its
ability to find new heuristics and new kinds of attributes that are worth
using; it does this by generalizing individual experiences (compiled
hindsight), by specializing previously-known generalities, and by
analogizing to concepts, heuristics, and slots of other fields, and to the
PATHS which were followed to produce them.
(3) The results of experiments such as these, and earlier ones in
automatic programming, led to a radical hypothesis about biological
evolution, namely that long before a three billion line DNA "program"
would have evolved through random generation of mutations, nature may have
happened upon a much more efficacious -- yet scarcely more complicated --
scheme for skewing mutations along plausible paths, namely the method of
heuristic search. The hypothesis is described in [20]; there is little
teleology in it: "plausible" means simply consistent with a record of the
species' genetic history.
The initial focus in the coming three years will be on Eurisko: extending
it, performing experiments on it. As new successes and limitations
appear, the "theory of heuristics" can be furthered. To a lesser degree,
the extension of the RLL (representation language language) tool will be
pursued; our major interest is in its use for Eurisko, not as an end in
itself.
I have to date served on several Ph.D reading committees, orals
committees, and departmental committees. My current PhD students are Russ
Greiner, Dave Smith, and Colleen Crangle (special program), and I am
co-advising Greg Cooper (special program). I am supervising research by
Dr. Jack Mostow (a research associate) and by several master's students.
Teaching has included
1978/79: CS206, CS224, CS229.
1979/80: CS222, CS224, CS101, and CS301.
(1980/81: CS222, CS224, CS301.)
The CS229 course was a new seminar on heuristics and problem-solving,
co-taught with Professor Polya. CS301 and CS101 were co-taught with
Professor Feigenbaum. CS301 is a new course we introduced last Spring, a
seminar on entering the computer science profession (teaching and writing
skills, choosing a thesis topic, funding, consulting, academia vs.
industry, etc.)
External References
Robert Balzer, Information Sciences Institute, Los Angeles, Ca.
W. W. Bledsoe, Math Department, U. Texas at Austin
John Seely Brown, XEROX PARC, Palo Alto, Ca.
Randall Davis, Computer Sci. Dept., MIT, Cambridge, Mass.
Adrian de Groot, Amsterdam, Netherlands
Bernard Meltzer, Artificial Intelligence Dept., U. of Edinbugh, Scotland
Raj Reddy, Computer Science Dept., Carnegie-Mellon University, Pgh., Pa.
Pat Winston, Computer Science Dept., MIT, Cambridge, Mass.
Biography
Douglas B. Lenat was born in Philadelphia, and attended the University of
Pennsylvania, where he received B.A. dgrees in math and physics, and a
M.S. in applied math. His graduate training was in computer science at
Stanford U., and he received his Ph.D. in 1976. His thesis was a
demonstration that certain kinds of "creative discoveries" in mathematics
could be produced by a computer program (a theorem proposer, rather than a
theorem prover). Lenat then went to Carnegie-Mellon University as an
assistant professor of computer science, and has recently taken that same
position at Stanford University. In August, 1977, Lenat was awarded the
biannual Computers & Thought Award by the International Joint Committee on
Artificial Intelligence. His current research deals with the question of
how to discover not merely mathematical conjectures, but informal rules of
thumb as well. In August, 1982, Lenat received the Tioga Award for Best
Paper at the American Association for AI conference.